{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Triangle Area"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestTriangleArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大三角形面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <strong>X-Y</strong> 平面上的点组成的数组 <code>points</code> ，其中 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 <code>10<sup>-5</sup></code> 内的答案将会视为正确答案<strong>。</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/04/1027.png\" style=\"height: 369px; width: 450px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[0,0],[0,1],[1,0],[0,2],[2,0]]\n",
    "<strong>输出：</strong>2.00000\n",
    "<strong>解释：</strong>输入中的 5 个点如上图所示，红色的三角形面积最大。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,0],[0,0],[0,1]]\n",
    "<strong>输出：</strong>0.50000\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= points.length &lt;= 50</code></li>\n",
    "\t<li><code>-50 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 50</code></li>\n",
    "\t<li>给出的所有点 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-triangle-area](https://leetcode.cn/problems/largest-triangle-area/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-triangle-area](https://leetcode.cn/problems/largest-triangle-area/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[0,1],[1,0],[0,2],[2,0]]', '[[1,0],[0,0],[0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        return max(0.5 * ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) for x1, y1 in points for x2, y2 in points for x3, y3 in points)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:\n",
    "            return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2\n",
    "        return max(triangleArea(x1, y1, x2, y2, x3, y3) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:\n",
    "            return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2\n",
    "        return max(triangleArea(x1, y1, x2, y2, x3, y3) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from itertools import combinations\n",
    "# class Solution:\n",
    "#     def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "#         l = 0  #保存目前最大的面积的值\n",
    "#         for (x1,y1),(x2,y2),(x3,y3) in combinations(points,3):\n",
    "#             l2 = abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2\n",
    "#             if l2 >= l:\n",
    "#                 l = l2\n",
    "#         return l\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        l = 0  #保存目前最大的面积的值\n",
    "        for i in range(len(points)):\n",
    "            x1,y1 = points[i]\n",
    "            for j in range(i+1,len(points)):\n",
    "                x2,y2 = points[j]\n",
    "                for k in range(j+1,len(points)):\n",
    "                    x3,y3 = points[k]\n",
    "                    l2 = abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2\n",
    "                    if l2 >= l:\n",
    "                        l = l2\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        return max(abs((x0-x2)*(y1-y2)-(x1-x2)*(y0-y2))for(x0,y0),(x1,y1),(x2,y2) in combinations(points,3))/2\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:\n",
    "            return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2\n",
    "        return max(triangleArea(x1, y1, x2, y2, x3, y3) for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        n = len(points)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if points[i] != points[j] and points[j] != points[k] and points[i] != points[k]:\n",
    "                        x1,y1 = points[i][0],points[i][1]\n",
    "                        x2,y2 = points[j][0],points[j][1]\n",
    "                        x3,y3 = points[k][0],points[k][1]\n",
    "                        ans = max(ans, 0.5 * (x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        return max(abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2 for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 选点选出最大的三角形面积\n",
    "# 尝试使用三重循环进行遍历\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        n = len(points)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                for k in range(j+1, n):\n",
    "                    print(i, j, k)\n",
    "                    temp = abs( points[i][0]*(points[j][1]-points[k][1]) + points[j][0]*(points[k][1]-points[i][1]) + points[k][0]*(points[i][1]-points[j][1]) )\n",
    "                    if temp > ans:\n",
    "                        ans = temp\n",
    "        return ans * 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "from itertools import combinations\r\n",
    "from functools import cmp_to_key\r\n",
    "class Solution1:\r\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\r\n",
    "        res = 0.0\r\n",
    "        for (x1, y1), (x2, y2), (x3, y3) in combinations(points, 3):\r\n",
    "            area = 0.5 * abs(x1*y2 + y1*x3 + x2*y3 - y1*x2 - y2*x3 - y3*x1)\r\n",
    "            res = max(res, area)\r\n",
    "        return res\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\r\n",
    "        def triangleArea(x1: int, y1: int, x2: int, y2: int, x3: int, y3: int) -> float:\r\n",
    "            return abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2\r\n",
    "\r\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\r\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\r\n",
    "        def distance(p: List[int], q: List[int]) -> int:\r\n",
    "            return (q[0] - p[0]) * (q[0] - p[0]) + (q[1] - p[1]) * (q[1] - p[1])\r\n",
    "\r\n",
    "        def findConvexHull(points: List[List[int]]) -> List[int]:\r\n",
    "            bottom = 0\r\n",
    "            for i, point in enumerate(points):\r\n",
    "                if point[1] < points[bottom][1]:\r\n",
    "                    bottom = i\r\n",
    "            points[0], points[bottom] = points[bottom], points[0]\r\n",
    "            def cmp(a: List[int], b: List[int]) -> int:\r\n",
    "                diff = -cross(points[0], a, b)\r\n",
    "                return diff if diff else (distance(points[0], a) - distance(points[0], b))\r\n",
    "            points[1:] = sorted(points[1:], key=cmp_to_key(cmp))\r\n",
    "\r\n",
    "            n = len(points)\r\n",
    "            r = n - 1\r\n",
    "            while r >= 0 and cross(points[0], points[n-1], points[r]) == 0:\r\n",
    "                r -= 1\r\n",
    "            l, r = r + 1, n - 1\r\n",
    "            while l < r:\r\n",
    "                points[l], points[r] = points[r], points[l]\r\n",
    "                l += 1\r\n",
    "                r -= 1\r\n",
    "\r\n",
    "            stack = [0, 1]\r\n",
    "            for i in range(2, n):\r\n",
    "                while len(stack) > 1 and cross(points[stack[-2]], points[stack[-1]], points[i]) < 0:\r\n",
    "                    stack.pop()\r\n",
    "                stack.append(i)\r\n",
    "            return [points[i] for i in stack]\r\n",
    "\r\n",
    "        convex = findConvexHull(points)\r\n",
    "        res, n = 0, len(convex)\r\n",
    "        for i, p in enumerate(convex):\r\n",
    "            k = i + 2   # k increase when j increase, next k must beyond cur k when j change\r\n",
    "            for j in range(i + 1, n - 1):\r\n",
    "                q = convex[j]\r\n",
    "                while k + 1 < n:\r\n",
    "                    curArea = triangleArea(p[0], p[1], q[0], q[1], convex[k][0], convex[k][1])\r\n",
    "                    nextArea = triangleArea(p[0], p[1], q[0], q[1], convex[k+1][0], convex[k+1][1])\r\n",
    "                    if curArea >= nextArea:  # find extreme point since area_ij(k) is a convex function\r\n",
    "                        break\r\n",
    "                    k += 1\r\n",
    "                res = max(res, triangleArea(p[0], p[1], q[0], q[1], convex[k][0], convex[k][1]))\r\n",
    "\r\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\r\n",
    "        res = float('-inf')\r\n",
    "        def angleArea(a, b, c):\r\n",
    "            if a + b > c and b + c > a and a + c > b:\r\n",
    "                p = (a + b + c) / 2\r\n",
    "                return((p * (p - a) * (p - b) * (p - c)) ** 0.5)\r\n",
    "            return(0)\r\n",
    "\r\n",
    "        def distance(v1, v2):\r\n",
    "            return(((v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2) ** 0.5) \r\n",
    "\r\n",
    "        def backtrack(path, i):\r\n",
    "            nonlocal res\r\n",
    "            if len(path) == 3:\r\n",
    "                a = distance(path[0], path[1])\r\n",
    "                b = distance(path[0], path[2])\r\n",
    "                c = distance(path[1], path[2])\r\n",
    "                print(a, b, c)\r\n",
    "                res = max(res, angleArea(a, b, c))\r\n",
    "                return\r\n",
    "\r\n",
    "            for j in range(i, len(points)):\r\n",
    "                path.append(points[j])\r\n",
    "                backtrack(path, j + 1)\r\n",
    "                path.pop()\r\n",
    "\r\n",
    "        backtrack([], 0)\r\n",
    "\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        area=[]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for k in range(i+2,n):\n",
    "                    x1=points[j][0]-points[i][0]\n",
    "                    x2=points[k][0]-points[i][0]\n",
    "                    y1=points[j][1]-points[i][1]\n",
    "                    y2=points[k][1]-points[i][1]\n",
    "                    area.append(abs(x1*y2-x2*y1))\n",
    "        return max(area)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        def area_cal(p1, p2, p3):\n",
    "            return 1/2 * abs(p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1] - p1[0]*p3[1] - p2[0]*p1[1] -p3[0]*p2[1])\n",
    "        return max(area_cal(p1, p2, p3) for p1, p2, p3 in list(combinations(points, 3)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        s = 0\n",
    "        l = list(itertools.combinations(points, 3))\n",
    "        for ll in l:\n",
    "            x1 = float(ll[0][0])\n",
    "            x2 = float(ll[1][0])\n",
    "            x3 = float(ll[2][0])\n",
    "            y1 = float(ll[0][1])\n",
    "            y2 = float(ll[1][1])\n",
    "            y3 = float(ll[2][1])\n",
    "            S=0.5*abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))\n",
    "            if S > s:\n",
    "                s = S\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        ans = 0.0\n",
    "        n = len(points)\n",
    "        threes = list(combinations(range(n), 3))\n",
    "        for three in threes:\n",
    "            x1 = points[three[0]][0]\n",
    "            x2 = points[three[1]][0]\n",
    "            x3 = points[three[2]][0]\n",
    "            y1 = points[three[0]][1]\n",
    "            y2 = points[three[1]][1]\n",
    "            y3 = points[three[2]][1]\n",
    "\n",
    "            if (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1):\n",
    "                continue\n",
    "            else:\n",
    "                a = ((x2 - x1)**2 + (y2 - y1)**2)**0.5\n",
    "                b = ((x3 - x1)**2 + (y3 - y1)**2)**0.5\n",
    "                c = ((x3 - x2)**2 + (y3 - y2)**2)**0.5\n",
    "                p = (a + b + c) / 2\n",
    "                S = (p * (p - a) * (p - b) * (p - c))**0.5\n",
    "                ans = max(ans, S)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        def calculateArea(points: List[int]) -> float:\n",
    "            if points[0][0]==points[1][0]==points[2][0]:\n",
    "                return 0.0\n",
    "            if points[0][1]==points[1][1]==points[2][1]:\n",
    "                return 0.0\n",
    "            \n",
    "            a=sqrt((points[0][0]-points[1][0])**2+(points[0][1]-points[1][1])**2)\n",
    "            b=sqrt((points[1][0]-points[2][0])**2+(points[1][1]-points[2][1])**2)\n",
    "            c=sqrt((points[0][0]-points[2][0])**2+(points[0][1]-points[2][1])**2)\n",
    "            s = (a + b + c) / 2\n",
    "\n",
    "            if (s*(s-a)*(s-b)*(s-c))<0:\n",
    "                print(a)\n",
    "                print(b)\n",
    "                print(c)\n",
    "                print(s)\n",
    "                print(s)\n",
    "                print(s*(s-a)*(s-b)*(s-c))\n",
    "            \n",
    "            if abs(s*(s-a)*(s-b)*(s-c)) < 0.0000001:\n",
    "                return 0\n",
    "\n",
    "            return (s*(s-a)*(s-b)*(s-c)) ** 0.5\n",
    "\n",
    "        from itertools import combinations\n",
    "        comb=combinations(points,3)\n",
    "\n",
    "        res=0.0\n",
    "        for i in list(comb):\n",
    "            #print(i)\n",
    "            #print(type(i))\n",
    "            res=max(res, calculateArea(list(i)))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        import itertools as it\n",
    "        area = []\n",
    "        for e in it.combinations(points, 3):\n",
    "            # print(e)\n",
    "            x1,y1 = e[0]\n",
    "            x2,y2 = e[1]\n",
    "            x3,y3 = e[2]\n",
    "            s = 1/2 * abs((x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-x1*y3))\n",
    "            area.append(s)\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        list = []\n",
    "        for i in range(len(points) - 2):\n",
    "            for j in range(len(points) - i - 1):\n",
    "                for k in range(len(points) - i - j - 2):\n",
    "                    x1, y1 = points[i]\n",
    "                    x2, y2 = points[i + j + 1]\n",
    "                    x3, y3 = points[i + j + k + 2]\n",
    "                    a = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)\n",
    "                    b = math.sqrt((x2 - x3) ** 2 + (y2 - y3) ** 2)\n",
    "                    c = math.sqrt((x3 - x1) ** 2 + (y3 - y1) ** 2)\n",
    "                    if a + b > c and a + c > b and b + c > a:\n",
    "                        s = (a + b + c) / 2\n",
    "                        area = math.sqrt(s * (s - a) * (s - b) * (s - c))\n",
    "                        list.append(area)\n",
    "        return max(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        return max([abs((y[0] - x[0]) * (z[1] - x[1]) - (y[1] - x[1]) * (z[0] - x[0])) / 2 for x in points for y in points for z in points])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        import itertools\n",
    "        A=list(itertools.combinations(points,3))\n",
    "        ls1=[]\n",
    "        for i in A:\n",
    "            a=((i[0][0]-i[1][0])**2+(i[0][1]-i[1][1])**2)**0.5\n",
    "            b=((i[0][0]-i[2][0])**2+(i[0][1]-i[2][1])**2)**0.5\n",
    "            c=((i[1][0]-i[2][0])**2+(i[1][1]-i[2][1])**2)**0.5\n",
    "            p=(a+b+c)/2\n",
    "            s=(p*(p-a)*(p-b)*(p-c))**0.5\n",
    "            ls1.append(abs(s))\n",
    "        ls1.sort()    \n",
    "        return ls1[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        l = list(combinations(points, 3))\n",
    "        s = []\n",
    "        for x in l:\n",
    "            x1 = x[0][0]\n",
    "            y1 = x[0][1]\n",
    "            x2 = x[1][0]\n",
    "            y2 = x[1][1]\n",
    "            x3 = x[2][0]\n",
    "            y3 = x[2][1]\n",
    "            ss = (1 / 2) * (x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2)\n",
    "            s.append(abs(ss))\n",
    "        return max(s)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_square(p1, p2, p3):\n",
    "    s = abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - p1[0] * p3[1] - p2[0] * p1[1] - p3[0] * p2[1])\n",
    "\n",
    "    print(s)\n",
    "    return s/2\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        # 获取x的最大值和最小值\n",
    "        # 获取y的最大值和最小值\n",
    "        combinations = list(itertools.combinations(points, 3))\n",
    "        # print(combinations)\n",
    "        s = 0\n",
    "        for c in combinations:\n",
    "            print(c)\n",
    "            s = max(s,get_square(*c))\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        res = []\n",
    "        result = []\n",
    "        for i in itertools.combinations(points,3):\n",
    "            res.append(i)\n",
    "        for j in res:\n",
    "            result.append(0.5*abs(j[0][0]*j[1][1]+j[1][0]*j[2][1]+j[2][0]*j[0][1]-j[2][0]*j[1][1]-j[1][0]*j[0][1]-j[0][0]*j[2][1]))\n",
    "        return max(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        l = len(points)\n",
    "        \n",
    "        t = []\n",
    "        \n",
    "        for a in range(l-2):\n",
    "            for b in range(a+1, l-1):\n",
    "                for c in range(b+1, l):\n",
    "                    t.append([a, b, c])\n",
    "        \n",
    "        s = []\n",
    "        \n",
    "        for x in t:\n",
    "            a, b, c = x\n",
    "            a, b, c = points[a], points[b], points[c]\n",
    "            m0 = ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5\n",
    "            m1 = ((a[0] - c[0]) ** 2 + (a[1] - c[1]) ** 2) ** 0.5\n",
    "            m2 = ((c[0] - b[0]) ** 2 + (c[1] - b[1]) ** 2) ** 0.5\n",
    "            p = (m0 + m1 + m2) / 2\n",
    "            area = p * (p - m0) * (p - m1) * (p - m2)\n",
    "            if area >= 0:\n",
    "                area = area ** 0.5\n",
    "                s.append(area)\n",
    "        \n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import sqrt\n",
    "from itertools import combinations as cs\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: list[list[int]]) -> float:\n",
    "        def ss(d):\n",
    "            a1 = d[0][0]-d[1][0] if d[0][0] > d[1][0] else d[1][0]-d[0][0]\n",
    "            a2 = d[0][1]-d[1][1] if d[0][1] > d[1][1] else d[1][1]-d[0][1]\n",
    "            a = sqrt(a1**2+a2**2)\n",
    "\n",
    "            b1 = d[2][0]-d[1][0] if d[2][0] > d[1][0] else d[1][0]-d[2][0]\n",
    "            b2 = d[2][1]-d[1][1] if d[2][1] > d[1][1] else d[1][1]-d[2][1]\n",
    "            b = sqrt(b1**2+b2**2)\n",
    "\n",
    "            c1 = d[2][0]-d[0][0] if d[2][0] > d[0][0] else d[0][0]-d[2][0]\n",
    "            c2 = d[2][1]-d[0][1] if d[2][1] > d[0][1] else d[0][1]-d[2][1]\n",
    "            c = sqrt(c1**2+c2**2)\n",
    "\n",
    "            p = (a+b+c)/2 # 周长的一半\n",
    "            for i in (p-a,p-b,p-c):\n",
    "                if i < 0:\n",
    "                    return 0\n",
    "            else:\n",
    "                s = round(sqrt(p*(p-a)*(p-b)*(p-c)),6)  # 面积\n",
    "                return s\n",
    "        d = list(cs(points,3))\n",
    "        return max(list(map(ss,d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def length(self,p1,p2,p3):\n",
    "        a = ((p2[1]-p1[1])**2+(p2[0]-p1[0])**2)**0.5\n",
    "        b = ((p3[1]-p1[1])**2+(p3[0]-p1[0])**2)**0.5\n",
    "        c = ((p3[1]-p2[1])**2+(p3[0]-p2[0])**2)**0.5\n",
    "        return a,b,c\n",
    "    def area(self,p1,p2,p3):\n",
    "        a,b,c = self.length(p1,p2,p3)\n",
    "        p = (a+b+c)/2\n",
    "        area = p*(p-a)*(p-b)*(p-c)\n",
    "        if area<0:\n",
    "            return 0\n",
    "        else:\n",
    "            return area**0.5\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        ret = []\n",
    "        def backtrack(points,tmp):\n",
    "            if len(tmp)==3:\n",
    "                #print(tmp)\n",
    "                ret.append(self.area(tmp[0],tmp[1],tmp[2]))\n",
    "                return \n",
    "            for i in range(len(points)):\n",
    "                if len(tmp)+len(points[i:])<3:break\n",
    "                backtrack(points[i+1:],tmp+[points[i]])\n",
    "        backtrack(points,[])\n",
    "        return max(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "    res = []\n",
    "    length = len(points)\n",
    "    for i in range(length):\n",
    "      p1 = points[i]\n",
    "      for j in range(length):\n",
    "        p2 = points[j]\n",
    "        for k in range(length):\n",
    "          p3 = points[k]\n",
    "          if ((p1[0] - p2[0]) * (p1[1] - p3[1])) != ((p1[0] - p3[0]) * (p1[1] - p2[1])):\n",
    "            res.append((p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])) / 2)\n",
    "    return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        square_list=[]\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                for k in points:\n",
    "                    square_2=abs(i[0]*j[1]-i[0]*k[1]+j[0]*k[1]-j[0]*i[1]+k[0]*i[1]-k[0]*j[1])\n",
    "                    square_list.append(square_2)\n",
    "        return max(square_list)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        combinations = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i, len(points)):\n",
    "                for k in range(j, len(points)):\n",
    "                    combinations.append([points[i], points[j], points[k]])\n",
    "        area = []\n",
    "        for i in combinations:\n",
    "            a = [i[1][0]-i[0][0], i[1][1]-i[0][1]]\n",
    "            b = [i[2][0]-i[0][0], i[2][1]-i[0][1]]\n",
    "            area.append(abs(a[0]*b[1]-a[1]*b[0])*0.5)\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        combinations = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(i, len(points)):\n",
    "                for k in range(j, len(points)):\n",
    "                    combinations.append([points[i], points[j], points[k]])\n",
    "        area = []\n",
    "        res = 0\n",
    "        for i in combinations:\n",
    "            a = [i[1][0]-i[0][0], i[1][1]-i[0][1]]\n",
    "            b = [i[2][0]-i[0][0], i[2][1]-i[0][1]]\n",
    "            if abs(a[0]*b[1]-a[1]*b[0])*0.5 > res:\n",
    "                res = abs(a[0]*b[1]-a[1]*b[0])*0.5\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_square(p1, p2, p3):\n",
    "    s = abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - p1[0] * p3[1] - p2[0] * p1[1] - p3[0] * p2[1])\n",
    "    return s/2\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        combinations = list(itertools.combinations(points, 3))\n",
    "        s = 0\n",
    "        for c in combinations:\n",
    "            s = max(s,get_square(*c))\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations as p        \n",
    "def f(points:list)->float:\n",
    "    return max([(1/2)*(x[0]*y[1]+y[0]*z[1]+z[0]*x[1]-x[0]*z[1]-y[0]*x[1]-z[0]*y[1]) for x,y,z in p(points,3)])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        return f(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        import math\n",
    "        import itertools\n",
    "        a = 0\n",
    "        b = 0\n",
    "        def f(A,B,C):\n",
    "            a = math.sqrt((A[0]-B[0])**2 + (A[1]-B[1])**2)\n",
    "            b = math.sqrt((A[0]-C[0])**2 + (A[1]-C[1])**2)\n",
    "            c = math.sqrt((B[0]-C[0])**2 + (B[1]-C[1])**2)\n",
    "            s =(a + b +c)/2\n",
    "            area = math.sqrt(abs(s * (s-a) * (s-b) * (s-c)))\n",
    "            return area\n",
    "        combinations = list(itertools.combinations(points, 3))\n",
    "        for i in combinations:\n",
    "            a = f(i[0],i[1],i[2])\n",
    "            if a > b:\n",
    "                b = a\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-            \n",
    "# @Time : 2023/9/30 11:29\n",
    "# @Author:yhq\n",
    "# @FileName: LC_812_最大三角形面积.py\n",
    "# @Software: 2023 Python 编程能力提升专项\n",
    "import itertools\n",
    "import math\n",
    "import sys\n",
    "import time\n",
    "from typing import List\n",
    "import itertools\n",
    "\n",
    "debug = False\n",
    "'''\n",
    "题目描述:\n",
    "\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        '''\n",
    "        :param points:\n",
    "        :return:\n",
    "        '''\n",
    "        # 1、获得列表中三个点可能存在的组合。要求不重复。\n",
    "        point_combine_lst = []\n",
    "        point_combine = itertools.combinations(points, 3)\n",
    "\n",
    "        for p in point_combine:\n",
    "            point_combine_lst.append(p)\n",
    "\n",
    "        if debug:\n",
    "            print(\"可能组合列表:\", point_combine_lst)\n",
    "\n",
    "        # 2、根据行列式方法求取三角形面积  s=abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)/2\n",
    "        area_lst = []\n",
    "        for combine in point_combine_lst:\n",
    "            a_x, a_y = combine[0][0], combine[0][1]\n",
    "            b_x, b_y = combine[1][0], combine[1][1]\n",
    "            c_x, c_y = combine[2][0], combine[2][1]\n",
    "            s_temp = abs(a_x * b_y + b_x * c_y + c_x * a_y - a_x * c_y - b_x * a_y - c_x * b_y) / 2\n",
    "            area_lst.append(s_temp)\n",
    "        if debug:\n",
    "            print(\"所有的面积信息:\", area_lst)\n",
    "        #3、max函数如果遇到空列表啥的,会抛错误,所以需要加一个default值处理\n",
    "        return max(area_lst, default=0.0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                for k in range(len(points)):\n",
    "                    area.append(abs(points[i][0]*points[j][1]+points[j][0]*points[k][1]+points[k][0]*points[i][1]-points[j][0]*points[i][1]-points[k][0]*points[j][1]-points[i][0]*points[k][1])*0.5)\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        cross = lambda x1,y1,x2,y2:x1*y2-x2*y1\n",
    "        area  = lambda a,b,c:cross(b[0]-a[0],b[1]-a[1],c[0]-a[0],c[1]-a[1])\n",
    "        return max([abs(area(a,b,c)) for a in points for b in points for c in points])/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        s=[]\n",
    "        for a in points:\n",
    "            for b in points:\n",
    "                for c in points:\n",
    "                    s.append(a[0]*b[1]+b[0]*c[1]+c[0]*a[1]-a[0]*c[1]-b[0]*a[1]-c[0]*b[1])\n",
    "            m = max(s)/2\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        res = []\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(points)):\n",
    "                for k in range(len(points)):\n",
    "                    x1,y1 = points[i]\n",
    "                    x2,y2 = points[j]\n",
    "                    x3,y3 = points[k]\n",
    "                    res.append(abs(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2))\n",
    "        return max(res)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        cross = lambda x1,y1,x2,y2:x1*y2-x2*y1\n",
    "        area  = lambda a,b,c:cross(b[0]-a[0],b[1]-a[1],c[0]-a[0],c[1]-a[1])\n",
    "        return max([abs(area(a,b,c)) for a in points for b in points for c in points])/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "\n",
    "        area = []\n",
    "        \n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        s=[]\n",
    "        for i in range(len(points)-2):\n",
    "            for j in range(len(points)-1):\n",
    "                for k in range(len(points)):\n",
    "                    a=0.5*((points[i][0]*points[j][1]+points[j][0]*points[k][1]+points[k][0]*points[i][1])-(points[i][1]*points[j][0]+points[j][1]*points[k][0]+points[k][1]*points[i][0]))\n",
    "                    s.append(abs(a))\n",
    "        return max(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        newlist=[]\n",
    "        def mianji(x1,y1,x2,y2,x3,y3):\n",
    "            s=abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2) / 2\n",
    "            return s      \n",
    "        for (x1,y1) in points:\n",
    "            for (x2,y2) in points:\n",
    "                if (x1,y1)==(x2,y2):\n",
    "                    continue\n",
    "                for (x3,y3) in points:\n",
    "                    if (x3,y3)==(x1,y1) or (x3,y3)==(x2,y2):\n",
    "                        continue\n",
    "                    newlist.append(mianji(x1,y1,x2,y2,x3,y3))\n",
    "        return max(newlist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        area = []\n",
    "        for i in points:\n",
    "            for j in points:\n",
    "                if i != j:\n",
    "                    for k in points:\n",
    "                        if i != k and j != k:\n",
    "                            a = sqrt((i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2)\n",
    "                            b = sqrt((i[0] - k[0]) ** 2 + (i[1] - k[1]) ** 2)\n",
    "                            c = sqrt((j[0] - k[0]) ** 2 + (j[1] - k[1]) ** 2)\n",
    "                            p = (a + b + c)/2\n",
    "                            area.append(sqrt(p*abs(p-a)*abs(p-b)*abs(p-c)))\n",
    "        return max(area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "\n",
    "        def trans(a,b,c):\n",
    "            if a==b or b==c or a==c:\n",
    "                return -1\n",
    "            x1,y1 = b[0]-a[0], b[1]-a[1]\n",
    "            x2,y2 = b[0]-c[0], b[1]-c[1]\n",
    "            return abs(x1*y2-x2*y1)/2\n",
    "\n",
    "        d = collections.Counter([trans(a,b,c) for a in points for b in points for c in points])\n",
    "        return max(d.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def AreaOfTreePoints(self, points: List[List[int]]) -> float:\n",
    "        x1, y1 = points[0]\n",
    "        x2, y2 = points[1]\n",
    "        x3, y3 = points[2]\n",
    "        A = abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))/2\n",
    "        return A\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        if len(points) == 3:\n",
    "            return self.AreaOfTreePoints(points)\n",
    "        else:\n",
    "            A = []\n",
    "            for p1 in points:\n",
    "                for p2 in points:\n",
    "                    for p3 in points:\n",
    "                        p_list = [p1, p2, p3]\n",
    "                        A.append(self.AreaOfTreePoints(p_list))\n",
    "            return max(A)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def summer(self,p1:List,p2:List,p3:List):\n",
    "        return 0.5*abs(p1[0]*p2[1]+p2[0]*p3[1]+p3[0]*p1[1]-p1[0]*p3[1]-p2[0]*p1[1]-p3[0]*p2[1])\n",
    "\n",
    "    def largestTriangleArea(self, points: List[List[int]]) -> float:\n",
    "        n=len(points)\n",
    "        li=[]\n",
    "        for i in range(n-2):\n",
    "            for j in range(1,n-1):\n",
    "                for k in range(2,n):\n",
    "                    ans=self.summer(points[i],points[j],points[k])\n",
    "                    li.append(ans)\n",
    "        return max(li)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
